
struct coor {
	double x, y;
	coor(double xx=0, double yy=0): x(xx), y(yy) {}
	bool operator< (const coor &p) const {
		return (x+eps<p.x || (abs(x-p.x)<eps && y+eps<p.y));
	}
};

/*double min(double x, double y) {
    if (x+eps<y) return x; return y;
}

double max(double x, double y) {
    return -min(-x,-y);
}*/

struct line {
	double a,b,c;

	line(double aa=0, double bb=0, double cc=0): a(aa), b(bb), c(cc) {}
	line(const coor &p, const coor &q) {
		a=p.y-q.y;
		b=q.x-p.x;
		c=-a*p.x-b*p.y;
		norm();
	}

	void norm() {
		double tmp=sqrt(a*a+b*b);
		if (abs(tmp)>eps)
			a/=tmp, b/=tmp, c/=tmp;
	}

	double dist(const coor &p) const {
		return a*p.x+b*p.y+c;
	}
};

////////////////////////////////////////////////////////////////
double determinant(double a, double b, double c, double d) {
	return a*d-b*c;
}

bool intersectline (line m, line n, coor &ans) {
	double tmp=determinant(m.a,m.b,n.a,n.b);
	if (abs(tmp)<eps) return false;
	ans.x=-determinant(m.c,m.b,n.c,n.b)/tmp;
	ans.y=-determinant(m.a,m.c,n.a,n.c)/tmp;
	return true;
}

bool parallel (line m, line n) {
	return abs(determinant(m.a,m.b,n.a,n.b))<eps;
}

bool equivalent (line m, line n) {
	return (abs(determinant(m.a,m.b,n.a,n.b))<eps
		&& abs(determinant(m.a,m.c,n.a,n.c))<eps
		&& abs(determinant(m.b,m.c,n.b,n.c))<eps);
}

bool between1d (double l, double r, double x) {
	return (min(l,r)<=x+eps && x<=max(l,r)+eps);
}

bool intersect1d (double a, double b, double c, double d) {
	if (a>b) swap(a,b);
	if (c>d) swap(c,d);
	return (max(a,c)<=min(b,d)+eps);
}

bool intersectseg (coor a, coor b, coor c, coor d, coor &left, coor &right) {
	if (!intersect1d (a.x,b.x,c.x,d.x) || !intersect1d (a.y,b.y,c.y,d.y)) return false;
	line m(a,b);
	line n(c,d);
	double tmp=determinant(m.a, m.b,n.a,n.b);
	if (abs(tmp)<eps) {
		if (abs(m.dist(c))>eps || abs (n.dist(a))>eps) return false;
		if (b<a) swap(a,b);
		if (d<c) swap(c,d);
		left=max(a,c);
		right=min(b,d);
		return true;
	}
	else {
		left.x =right.x=-determinant(m.c,m.b,n.c,n.b)/tmp;
		left.y =right.y=-determinant(m.a,m.c,n.a,n.c)/tmp;
		return between1d(a.x,b.x,left.x)
			&& between1d(a.y,b.y,left.y)
			&& between1d(c.x,d.x,left.x)
			&& between1d(c.y,d.y,left.y);
	}
}

bool cirsectline(coor center, double r, line m, coor &p1, coor &p2) {
    m.c+=m.a*center.x+m.b*center.y;
    double x0=-m.a*m.c/(sqr(m.a)+sqr(m.b)), y0=-m.b*m.c/(sqr(m.a)+sqr(m.b));
    if (sqr(m.c)>sqr(r)*(sqr(m.a)+sqr(m.b))+eps) return false;
    else
        if (abs(sqr(m.c)-sqr(r)*(sqr(m.a)+sqr(m.b)))<eps) {
            p1.x=p2.x=x0;
            p1.y=p2.y=y0;
        }
        else {
            double d=sqr(r)-sqr(m.c)/(sqr(m.a)+sqr(m.b));
            double mult=sqrt(d/(sqr(m.a)+sqr(m.b)));
            p1.x=x0+m.b*mult;
            p2.x=x0-m.b*mult;
            p1.y=y0-m.a*mult;
            p2.y=y0+m.a*mult;
        }
    p1.x+=center.x; p2.x+=center.x;
    p1.y+=center.y; p2.y+=center.y;
    return true;
}

bool cirsectcir (coor center1, double r1, coor center2, double r2, coor &p1, coor &p2) {
        if (abs(center1.x-center2.x)<eps && abs(center1.y-center2.y)<eps)
            if (abs(r1-r2)<eps) return true; else return false;
        center2.x-=center1.x; center2.y-=center1.y;
        line m(-2*center2.x, -2*center2.y, sqr(center2.x)+sqr(center2.y)+sqr(r1)-sqr(r2));
        coor tmp;
        bool ans=cirsectline(tmp,r1,m,p1,p2);
        p1.x+=center1.x; p2.x+=center1.x;
        p1.y+=center1.y; p2.y+=center1.y;
        return ans;
}

double ccw (const coor &a, const coor &b, const coor &c) {
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

//counter clockwise otder
void convexhull (vector<coor> a, vector<coor> &hull) {
    int n=0;
    sort(all(a));
    fora(i,a) {
        while (n>=2 && ccw(hull[n-2],hull[n-1],a[i])<=0) {
            hull.pop_back();
            n--;
        }
        hull.pb(a[i]);
        n++;
    }
    for(int i=sz(a)-2,k=n+1; i>=0; i--) {
        while (n>=k && ccw(hull[n-2],hull[n-1],a[i])<=0) {
            hull.pop_back();
            n--;
        }
        hull.pb(a[i]);
        n++;
    }
}

bool ptinhull(const vector<coor> &hull, const coor &p) {
        int bottom=0, top=n-1;
        while (bottom<=top) {
            int mid=(bottom+top)>>1;
            if (ccw(a[bottom],a[mid],p)<=0) top=mid-1; else bottom=mid+1;
        }
        return (ccw(a[top],a[bottom],p)<0);
}

